"""
https://leetcode.cn/problems/largest-number/description/

179. 最大数
中等
相关标签
相关企业
给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。

注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。

 

示例 1：

输入：nums = [10,2]
输出："210"
示例 2：

输入：nums = [3,30,34,5,9]
输出："9534330"
 

提示：

1 <= nums.length <= 100
0 <= nums[i] <= 109

"""

from typing import List


class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        """
        核心是出compare方法。
        如果存在：AB和A的形式，如果A>B，则认为A更大，否则AB更大
        如果存在：ABC和AB的形式，如果B>C，则认为AB更大,否则ABC更大
        """
        if len(nums)==1:
            return str(nums[0])

        def compare(s1,s2):
            # 不需要考虑那么多，直接s1+s2和s2+s1对比即可
            sum1=f'{s1}{s2}'
            sum2=f'{s2}{s1}'
            for i in range(len(sum1)):
                c1=sum1[i]
                c2=sum2[i]
                if ord(c1)<ord(c2):
                    return -1
                elif ord(c1)>ord(c2):
                    return 1
                else:
                    i+=1
            return 0

            # i=0
            # while i<len(s1) or i<len(s2):
            #     c1=s1[i] if i<len(s1) else s1[-1]
            #     c2=s2[i] if i<len(s2) else s2[-1]
            #     if ord(c1)<ord(c2):
            #         return -1
            #     elif ord(c1)>ord(c2):
            #         return 1
            #     else:
            #         i+=1
            # return 0
        
        def merge(left,right):
            res=[]
            i1=i2=0
            while i1<len(left) and i2<len(right):
                if compare(left[i1],right[i2])>=0:
                    res.append(left[i1])
                    i1+=1
                else:
                    res.append(right[i2])
                    i2+=1
            while i1<len(left):
                res.append(left[i1])
                i1+=1
            while i2<len(right):
                res.append(right[i2])
                i2+=1
            return res

        def split_merge(arr,left,right):
            if left+1==right:
                return [arr[left]]
            mid=(left+right)//2
            left_res=split_merge(arr,left,mid)
            right_res=split_merge(arr,mid,right)
            return merge(left_res,right_res)

        arr=[str(_) for _ in nums]
        res=split_merge(arr,0,len(arr))

        res_str=''.join(res)
        nz=-1
        for i in range(len(res_str)-1):
            if res_str[i]!='0':
                nz=i
                break
        if nz>=0:


if __name__=='__main__':
    sol=Solution()
    nums=[34323,3432]
    res=sol.largestNumber(nums)
    print(res)
    pass